# -*-  coding: utf-8 -*-

class Node:
    def __init__(self, value=None, next=None):
        self.value, self.next = value, next


class LinkedList:
    def __init__(self, maxsize=None):
        self.maxsize = maxsize
        self.root = Node()  # 开始入口
        self.length = 0
        self.tailnode = None  # 尾节点

    def __len__(self):
        return self.length

    def append(self, value):  # O(1)
        if self.maxsize is not None and len(self) > self.maxsize:
            raise Exception('full')
        node = Node(value)  # 要插入的节点
        tailnode = self.tailnode
        if tailnode is None:
            self.root.next = node
        else:
            tailnode.next = node
        self.tailnode = node
        self.length += 1

    def appendleft(self, value):  # O(1)
        node = Node(value)  # 新生成的节点
        head_node = self.root.next
        self.root.next = node
        node.next = head_node
        self.length += 1

    def iter_node(self):  # 遍历所有元素
        curnode = self.root.next
        while curnode is not self.tailnode:
            yield curnode
            curnode = curnode.next
        yield curnode

    def __iter__(self):
        for node in self.iter_node():
            yield node.value

    def remove(self, value):  # O(n)
        prenode = self.root
        curnode = self.root.next
        while curnode is not None:
            if curnode.value == value:
                prenode.next = curnode.next  # 上一个节点的尾元素指向当前节点的下个元素
                if curnode is self.tailnode:
                    self.tailnode = prenode
                del curnode
                self.length -= 1
                return True
            else:
                prenode = curnode
            curnode = curnode.next
        return False

    # def remove(self, value):  # O(n)
    #     """ 删除包含值的一个节点，将其前一个节点的 next 指向被查询节点的下一个即可
    #
    #     :param value:
    #     """
    #     prevnode = self.root  #
    #     for curnode in self.iter_node():
    #         if curnode.value == value:
    #             prevnode.next = curnode.next
    #             if curnode is self.tailnode:  # NOTE: 注意更新 tailnode
    #                 self.tailnode = prevnode
    #             del curnode
    #             self.length -= 1
    #             return 1  # 表明删除成功
    #         else:
    #             prevnode = curnode
    #     return -1  # 表明删除失败

    def find(self, value):  # O(n)
        index = 0
        for node in self.iter_node():
            if node.value == value:
                return index
            index += 1
        return -1

    def popleft(self):  # O(1 )
        if self.root.next is None:
            raise Exception('pop from empty LinkedList')
        headnode = self.root.next
        self.root.next = headnode.next
        self.length -= 1
        value = headnode.value
        del headnode
        return value

    def clear(self):
        for node in self.iter_node():
            del node
        self.root.next = None
        self.length = 0


def test_linked_list():
    ll = LinkedList()
    ll.append(0)
    ll.append(1)
    ll.append(2)

    assert len(ll) == 3
    assert ll.find(2) == 2
    assert ll.find(3) == -1

    ll.remove(0)
    assert len(ll) == 2
    assert ll.find(0) == -1

    assert list(ll) == [1, 2]

    ll.appendleft(0)
    assert list(ll) == [0, 1, 2]
    assert len(ll) == 3

    headvalue = ll.popleft()
    assert headvalue == 0
    assert len(ll) == 2
    assert list(ll) == [1, 2]

    ll.append(3)
    ll.remove(2)
    assert len(ll) == 2
    assert ll.find(2) == -1
    assert list(ll) == [1, 3]

    ll.clear()
    assert len(ll) == 0
